package com.zhledu.datastructure.gragh;

import io.swagger.models.auth.In;
import lombok.extern.slf4j.Slf4j;

import java.io.Serializable;
import java.util.*;

@Slf4j
public class MyAMGragh {
    private final static int MaxVnum = 10;
    private final static int MAX_INT = Integer.MAX_VALUE;
    /**
     * 记录某个顶点到其他节点的前驱节点下标
     */
    private int[] pre = new int[MaxVnum];
    /***
     * 记录开始节点到其他节点的距离
     */
    private int[] dist = new int[MaxVnum];
    /***
     * 记录某个节点是否加入战队
     */
    private boolean[] flag = new boolean[MaxVnum];

    private class AMGragh {
        public Serializable vex[] = new Serializable[MaxVnum];
        public int edge[][] = new int[MaxVnum][MaxVnum];
        public int vexnum, edgenum;
    }

    boolean visited[] = new boolean[MaxVnum];

    private AMGragh g = new AMGragh();

    public void testInitGragh() {
        g.vexnum = 5;
        g.edgenum = 8;
        g.vex = "1,2,3,4,5".split(",");
        String info = "0,2,5,0,0:" +
                "0,0,2,6,0:" +
                "0,0,0,7,1:" +
                "0,0,2,0,4:" +
                "0,0,0,0,0";
        int i = 0;
        for (String s : info.split(":")) {
            String ss[] = s.split(",");
            for (int j = 0; j < ss.length; j++) {
                if (Integer.parseInt(ss[j]) == 0) {
                    g.edge[i][j] = MAX_INT;
                } else {
                    g.edge[i][j] = Integer.parseInt(ss[j]);
                }
            }
            i++;
        }

    }

    public void initGragh() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入顶点数和边数（空格隔开）");
        g.vexnum = scanner.nextInt();
        g.edgenum = scanner.nextInt();

        System.out.println("请依次输入" + g.vexnum + "个顶点信息");
        for (int i = 0; i < g.vexnum; i++) {
            g.vex[i] = scanner.next();
        }

        for (int i = 0; i < g.vexnum; i++) {
            for (int j = 0; j < g.vexnum; j++) {
                g.edge[i][j] = MAX_INT;
            }
        }
        System.out.println("请依次输入边的值，和该条边上的权值，以空格隔开：");
        while (g.edgenum-- > 0) {
            Serializable u = scanner.next();
            Serializable v = scanner.next();
            int w = scanner.nextInt();
            int i = locateVex(u);
            int j = locateVex(v);
            if (i != -1 && j != -1) {
                g.edge[i][j] = w;
            }
        }
    }

    private int locateVex(Serializable u) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.vex[i].equals(u)) {
                return i;
            }
        }
        return -1;
    }


    public void print() {
        System.out.println("打印顶点信息");
        for (int i = 0; i < g.vexnum; i++) {
            System.out.print(g.vex[i] + " ");
        }
        System.out.println();
        System.out.println("打印临界矩阵");
        for (int i = 0; i < g.vexnum; i++) {
            for (int j = 0; j < g.vexnum; j++) {
                if (g.edge[i][j] == MAX_INT) {
                    System.out.print("∞" + " ");
                } else {
                    System.out.print(g.edge[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }


    public void bfs(Serializable start) {
        List<Serializable> vex = new ArrayList<>();
        Queue<Serializable> queue = new ArrayDeque();
        int index = locateVex(start);
        visited[index] = true;
        vex.add(start);
        queue.offer(start);
        while (!queue.isEmpty()) {
            index = locateVex(queue.poll());
            for (int w = 0; w < g.vexnum; w++) {
                if (g.edge[index][w] != MAX_INT && !visited[w]) {
                    visited[w] = true;
                    vex.add(g.vex[w]);
                    queue.offer(g.vex[w]);
                }
            }
        }
        System.out.println("使用广度优先算法得到的点为：");
        for (Serializable point : vex) {
            System.out.print(point + "\t");
        }
        System.out.println();

    }

    public void dfs(Serializable start) {
        int v = locateVex(start);
        visited[v] = true;
        System.out.print(start + "\t");
        for (int w = 0; w < g.vexnum; w++) {
            if (g.edge[v][w] != MAX_INT && !visited[w]) {
                dfs(g.vex[w]);
            }
        }
    }

    public void dijkstra(Serializable start) {
        //找到开始节点的下标
        int index = locateVex(start);
        //1、设置数据结构，如果起点到其他节点的距离
        for (int i = 0; i < g.vexnum; i++) {
            dist[i] = g.edge[index][i];
            flag[i] = false;
            if (dist[i] == MAX_INT) {
                pre[i] = -1;
            } else {
                pre[i] = index;
            }
        }
        //自己到自己的距离是0
        dist[index] = 0;
        //初始的时候战队中只有开始节点一个节点
        flag[index] = true;
        //2、找源点中到每一个节点的最短距离
        for (int i = 0; i < g.vexnum; i++) {
            int min = MAX_INT;
            int t = index;
            for (int j = 0; j < g.vexnum; j++) {
                if (!flag[j] && dist[j] < min) {
                    min = dist[j];
                    t = j;
                }
            }
            //如果没有找到最短的节点
            if (t == index) {
                continue;
            } else {
                //把最短的那个节点加入战队
                flag[t] = true;
            }
            //3、更新与t相邻的顶点到源点的距离
            for (int j = 0; j < g.vexnum; j++) {
                if (!flag[j] && g.edge[t][j] < MAX_INT) {
                    if (dist[j] > dist[t] + g.edge[t][j]) {
                        dist[j] = dist[t] + g.edge[t][j];
                        pre[j] = t;
                    }
                }
            }
        }
    }

    public void findPath(Serializable start) {
        int x = 0;
        int index = locateVex(start);
        Stack<Integer> stack = new Stack<>();
        System.out.println("\n源点为：" + start);
        for (int i = 0; i < g.vexnum; i++) {
            x = pre[i];
            if (x == -1 && !start.equals(g.vex[i])) {
                System.out.println("源点" + start + "到" + g.vex[i] + "的距离的最短路劲为：无穷大");
                continue;
            } else {
                while (x != -1) {
                    stack.push(x);
                    x = pre[x];
                }
            }
            System.out.print("源点" + start + "到" + g.vex[i] + "的距离的最短路劲为：");
            while (!stack.isEmpty()) {
                System.out.print(g.vex[stack.pop()]+"-->");
            }
            System.out.println(g.vex[i]);
            System.out.println("最短距离是："+dist[i]);
        }
    }


    public static void main(String[] args) {
        MyAMGragh gragh = new MyAMGragh();
        gragh.testInitGragh();
        gragh.print();
        gragh.visited = new boolean[MaxVnum];
        gragh.bfs("1");
        gragh.visited = new boolean[MaxVnum];
        System.out.println("使用深度优先算法获得的顶点为：");
        gragh.dfs("1");
        gragh.dijkstra("1");
        gragh.findPath("1");
    }


}
